//============================================================================
// Name        : GSP295_Wk3_BinarySearch
// Author      : Ronald Ram
// Version     :
// Copyright   : GSP295 Wk3 Program - BinarySearch
// Description : Tree Implemented as Array, with a Binary Search in C++
//============================================================================


#include "BinarySeach.h"

namespace GSP295_Wk3
{
	//
	//Constructor
	GSP295_Wk3::BinarySeach::BinarySeach()
	{
		Init();
	}
	//
	//Init Method
	void GSP295_Wk3::BinarySeach::Init()
	{
		this->size = 0;
		//this->curr_position = 0;
		item = new string[MAX_ITEMS];

		for (int i=0; i< MAX_ITEMS; ++i)
		{
			item[i] = "NULL";
		}
	}
	//
	//Destrucotr
	GSP295_Wk3::BinarySeach::~BinarySeach()
	{
		delete [] item;
		this->size = 0;
	}
	//
	//
	
	////GSP295_Wk3::RelationType GSP295_Wk3::BinarySeach::ComparedTo( string item )
	////{
		////return GREATER;
	////}

	//
	//Clear the array and make ready for next round of Inserts|Deletes
	void GSP295_Wk3::BinarySeach::MakeEmpty()
	{
		delete [] item;
		Init();
	}
	//
	//Check if Array of Full
	bool GSP295_Wk3::BinarySeach::isFull() const
	{
		return (this->size >= MAX_ITEMS);
	}

	//
	//Return length of Array
	int GSP295_Wk3::BinarySeach::Length() const { return (this->size); }

	
	//Search Method
	//Search returns a result based on If INSERT or DELETE is calling it
	//IF input value matches, a +ve index is returned, otherwise a -ve
	int GSP295_Wk3::BinarySeach::Find( string &item, ActionType action )
	{
		int curr = 0, charIndex =0;

		//Index = -3:  Root is empty, OK to Insert		<-> Nothing to Delete
		//Index = -2: Can't Insert, Will cause Overflow <-> Nothing to Delete
		//Index = -1: Conflict, Can't Insert(Not Unique)
		//Index = 0+: Index found, OK to Insert			<-> OK to Delete
		int Index = -1;
		
		do 
		{
			if ( (const char*)item[curr] == "NULL" )
			{
				//Insert @ root, Nothing to Delete
				if ( action == INSERT || action == DELETE ) { Index = -3;
				}
				else { Index = curr; }

				break;
			} 
			//Check if this = item, starting @ root item
			else if ( this->item[curr] == item ) 
			{
				//Match found, OK to delete, Collision to Insert
				if ( action == INSERT ) { Index = -1;
				}
				else { Index = curr; }

				break;
			} 
			else 
			{
				//Check if this[first char] = item[first char]
				if ( ((Letter)this->item[curr][charIndex]) == ((Letter)item[charIndex]) ) 
				{
					//Check if this[2nd char] = item[2nd char]
					if ( ((Letter)this->item[curr][charIndex +1]) == ((Letter)item[charIndex +1]) ) 
					{
						//if 1st & 2nd chars equal then there is conflict in the tree, Can't Insert
						//if ( action == ActionType.INSERT || action == ActionType.DELETE )
						if ( action == INSERT || action == DELETE )
						{
							Index = -1; ////status = SearchStatus.CONF
						}
						else { Index = curr; }

						break;
					} 
					//Check if this[2nd char] > item[2nd char]
					//Go -> LEFT
					else if ( (Letter)this->item[curr][charIndex +1] > (Letter)item[charIndex +1] )  
					{
						//if ( action == ActionType.INSERT && (2 * curr + 1) > MAX_ITEMS )
						if ( action == INSERT && (2 * curr + 1) > MAX_ITEMS ) 
						{
							Index = -2;
							break;
						} 
						else { curr = 2 * curr + 1; }
					}
					//Go -> RIGHT
					else 
					{ 
						//if ( action == ActionType.INSERT && (2 * curr + 2) > MAX_ITEMS )
						if ( action == INSERT && (2 * curr + 2) > MAX_ITEMS ) 
						{
							Index = -2;
							break;
						} 
						else { curr = 2 * curr + 2; }
					}
				}
				//Compare first char of 'this' and 'input item', 
				//Go -> LEFT
				else if ( (Letter)this->item[curr][charIndex] > (Letter)item[charIndex] ) 
				{ 
					//if ( action == ActionType.INSERT && (2 * curr + 1) > MAX_ITEMS )
					if ( action == INSERT && (2 * curr + 1) > MAX_ITEMS ) 
					{
						Index = -2;
						break;
					} 
					else { curr = 2 * curr + 1; }
				}
				//Go -> RIGHT
				else 
				{ 
					//if ( action == ActionType.INSERT && (2 * curr + 2) > MAX_ITEMS )
					if ( action == INSERT && (2 * curr + 2) > MAX_ITEMS ) 
					{
						Index = -2;
						break;
					} 
					else { curr = 2 * curr + 2; } 
				}
			}
		} while ( curr <= MAX_ITEMS ); 
		//
		return Index;
	}



	//Insert method takes an input, calls the Find method
	//If there is match, then it is considered a collision and input is not made
	//If there is an OVER-FLOW insert is not made
	bool BinarySeach::Insert( string &item )
	{
		//Index = -3:  Root is empty, OK to Insert		<-> Nothing to Delete
		//Index = -2: Can't Insert, Will cause Overflow <-> Nothing to Delete
		//Index = -1: Conflict, Can't Insert(Not Unique)
		//Index = 0+: Index found, OK to Insert			<-> OK to Delete
		int Index = Find(item, INSERT); //ActionType.INSERT

		bool result = false;

		//Can't Insert, Conflict|OVERFLOW
		if ( Index == -2 || Index == -1 ) { result = false;
		} 
		//Insert @ root
		else if ( Index == 0) { this->item[Index] = item;  result = true;
		}
		return result;
	}
	//
	//Method takes input and search for a match
	//If match is found, element is deleted and child elements are bumped up one level
	bool BinarySeach::Delete( string &item )
	{
		//Index = -3:  Root is empty, OK to Insert		<-> Nothing to Delete
		//Index = -2: Can't Insert, Will cause Overflow <-> Nothing to Delete
		//Index = -1: Conflict, Can't Insert(Not Unique)
		//Index = 0+: Index found, OK to Insert			<-> OK to Delete
		int Index = Find(item, DELETE); //ActionType.DELETE
		int temp = 0;

		bool result = false;

		//Search found a Node..And Update Child Nodes
		if ( Index >= 0 ) 
		{ 
			for (int i= Index + 1; i< MAX_ITEMS; ++i)
			{
				this->item[i - 1] = this->item[i];
			}
			result = true;
		} 
		//Search = 'NO RESULT'
		else { result = false; }

		return result;
	}
	//
	//Print all elements in array Low->High Order 
	void BinarySeach::Print_InOrder()
	{
		inOrder(this->item);
	}

	//In-Order Traversal Used for Printing low->high values in array
	void BinarySeach::inOrder( string arr[] )
	{
		int index = 0;

		if ( arr[index] != "NULL" ) 
		{
			cout << "\n\n===================================\n" << endl;
			cout << "RESULTS PRINTOUT:" << endl;
			cout << "------------------------------------\n" << endl;
			
			index = 2 * index + 1;
			inOrder(arr);
			cout << arr[index] << " ";
			index = 2 * index + 2;
			inOrder(arr);
			
			cout << "\n\n===================================\n" << endl; 
		}
	}

}






